package com.atguigu.bsttree;

/**
 * 二叉排序树
 */
public class BstTree {

    Node root;

    public void addTreeNode(Node node){
        if (this.root == null){
            root = node;
            return;
        }else {
            root.addNode(node);
        }
    }

    public void order(){
        if (this.root == null){
            return;
        }else {
            root.order();
        }
    }

    public Node findTargetNode(int val){

        if (val == root.val){
            return root;
        }else {
            Node targetNode = root.findTargetNode(val);
            return targetNode;
        }
    }

    //查找父节点
    public Node findParentNode(Node node){
        if (node.val == root.val){
            return null;
        }else {
            Node parentNode = root.findParentNode(node);
            return parentNode;
        }
    }

    public static void main(String[] args) {
        int arr[] = {2,4,1,6,8,0};
        BstTree bstTree = new BstTree();
        for(int i=0;i<arr.length;i++){
            bstTree.addTreeNode(new Node(arr[i]));
        }
        bstTree.order();
        Node targetNode = bstTree.findTargetNode(2);
        Node parentNode = bstTree.findParentNode(targetNode);
        System.out.println(parentNode);
    }


}

class Node {
    int val;
    Node leftNode;
    Node rightNode;

    //找到目标节点
    public Node findTargetNode(int val){

        if (val == this.val){
            return this;
        }

        if (val < this.val){
            if (this.leftNode != null){
                return this.leftNode.findTargetNode(val);
            }

        }

        if (val >= this.val){
            if (this.rightNode != null){
                return this.rightNode.findTargetNode(val);
            }
        }
        return null;
    }

    //找到目标节点的父节点
    public Node findParentNode(Node node){

        if (node.val < this.val){
            if (this.leftNode.val == node.val){
                return this;
            }else {
                if (this.leftNode != null){
                    return this.leftNode.findParentNode(node);
                }

            }
        }

        if (node.val > this.val){
            if (this.rightNode.val == node.val){
                return this;
            }else {
                if (this.rightNode != null){
                    return this.rightNode.findParentNode(node);
                }

            }
        }

        return null;
    }

    public void addNode(Node no){
        if (no == null){
            return;
        }

        if (no.val < this.val){
            if (this.leftNode == null){
                this.leftNode = no;
            }else {
                this.leftNode.addNode(no);
            }
        }

        if (no.val >= this.val){
            if (this.rightNode == null){
                this.rightNode = no;
            }else {
                this.rightNode.addNode(no);
            }
        }
    }

    public void order(){
        if (this.leftNode != null){
            this.leftNode.order();
        }

        System.out.println(this.val);

        if (this.rightNode != null){
            this.rightNode.order();
        }
    }

    public Node(int val){
        this.val = val;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }
}
